package leetcode

import "math"

/*
 * @lc app=leetcode.cn id=84 lang=golang
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
func largestRectangleArea1(heights []int) int {
	n := len(heights)

	stack := []int{-1}
	left := make([]int, n)
	for i, v := range heights {
		for i := len(stack) - 1; i > 0 && heights[stack[i]] >= v; i = len(stack) - 1 {
			stack = stack[:i]
		}
		left[i] = stack[len(stack)-1]
		stack = append(stack, i)
	}
	stack = []int{n}
	right := make([]int, n)
	for i := n - 1; i > -1; i-- {
		v := heights[i]
		for i := len(stack) - 1; i > 0 && heights[stack[i]] >= v; i = len(stack) - 1 {
			stack = stack[:i]
		}
		right[i] = stack[len(stack)-1]
		stack = append(stack, i)
	}

	area := 0.0
	for i := 0; i < n; i++ {
		area = math.Max(area, float64((right[i]-left[i]-1)*heights[i]))
	}

	return int(area)
}

func largestRectangleArea2(heights []int) int {
	n := len(heights)

	stack := []int{-1}
	area := 0.0
	for j, v := range heights {
		for i := len(stack) - 1; i > 0 && heights[stack[i]] >= v; i = len(stack) - 1 {
			area = math.Max(area, float64((j-stack[i-1]-1)*heights[stack[i]]))
			stack = stack[:i]
		}
		stack = append(stack, j)
	}
	for i := len(stack) - 1; i > 0; i-- {
		area = math.Max(area, float64((n-stack[i-1]-1)*heights[stack[i]]))
	}

	return int(area)
}

func largestRectangleArea(heights []int) int {
	heights = append(heights, -1)

	stack := []int{-1}
	area := 0
	for j, v := range heights {
		for i := len(stack) - 1; i > 0 && heights[stack[i]] >= v; i = len(stack) - 1 {
			if tmpArea := (j - stack[i-1] - 1) * heights[stack[i]]; tmpArea > area {
				area = tmpArea
			}
			stack = stack[:i]
		}
		stack = append(stack, j)
	}

	return area
}

// @lc code=end
